package com.leetcode.easy;

import com.leetcode.entity.TreeNode;

/**
 * @Classname HasPathSum
 * @Description 路径总和
 * @Date 2020/9/20 15:57
 * @Created by zfl
 */
public class HasPathSum {

    /**
     * @param root
     * @param sum
     * @return
     * 深度优先算法
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        return help(root, sum);
    }

    /**
     * @param root
     * @param sum
     * @return
     * 叶子节点指既没有左子树又没有右子树的节点，否则不是叶子结点
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：38.9 MB, 在所有 Java 提交中击败了32.59%的用户
     */
    public boolean help(TreeNode root, int sum) {
        if(root == null) {
            return false;
        }

        if(root.left == null && root.right == null) {
            if(root.val == sum) {
                return true;
            }else{
                return false;
            }
        }
        /*if(root == null && sum == 0) {
            return true;
        }else if(root == null && sum != 0) {
            return false;
        }*/
        boolean left =  help(root.left,sum - root.val);
        boolean right = help(root.right, sum - root.val);
        if(left || right) {
            return true;
        }else {
            return false;
        }
    }

}
